package com.lcm.oj.base;

import java.util.LinkedHashMap;

/**
 * @author Coder-lcm
 * @date 2021/5/15
 *  排序算法汇总
 */
public class sort {
    public static void main(String[] args) {
        int[] nums = {1,4,2,6,75,23,67,23,56,23,41};
//        bubbleSort(nums);
//        selectSort(nums);
        insertSort(nums);
        for (int num : nums) {
            System.out.print(num + " ");
        }
    }

    /**n
     * 1. 冒泡排序
     * @param nums
     *
     * (1)比较前后相邻的二个数据,如果前面数据大于后面的数据,就将这二个数据交换。
     * (2)这样对数组的第0个数据到N-1个数据进行一次遍历后,最大的一个数据就“沉”到数组第N-1个位置
     * (3)N=N-1,如果N不为0就重复前面二步,否则排序完成。
     *
     *  时间复杂度：
     *      最好O（1）
     *      最坏O（n的平方）
     */
    public static void bubbleSort(int[] nums){
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            for (int i1 = 1; i1 < n - i; i1++) {
                if (nums[i1-1] > nums[i1]) {
                   swap(nums, i1, i1-1);
                }
            }
        }
    }

    /**
     * 2. 选择排序
     * @param nums
     *    每次从未排序的数中选出最小的数放到左边，依次往后
     * 时间复杂度:
     *      T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
     *
     */
    public static void selectSort(int[] nums){
        int len = nums.length;
        for (int i = 0; i < len; i++) { // 要比较n轮
            int minIndex = i;
            for (int i1 = i+1; i1 < len; i1++) { // 每一轮都要从右边部分找出最小的，然后放到左边
                if (nums[i1] < nums[minIndex]) {
                    minIndex = i1;
                }
            }
            if (i != minIndex) {
                swap(nums, i, minIndex);
            }
        }
    }

    /**
     * 插入排序，依次将后方的数插入到左方已排序的序列的合适位置
     * @param nums
     */
    public static void insertSort(int[] nums) {
        int len ;
        if (nums == null || (len = nums.length) <= 1) return;
        int insertNum;
        for (int i = 0; i < len; i++) {
            insertNum = nums[i];
            int j = i-1;
            while (j >= 0 && nums[j] > insertNum){
                nums[j+1] = nums[j];
                j--;
            }

            nums[j+1] = insertNum;
        }
    }




    /**
     * 交换
     * @param nums
     * @param a
     * @param b
     */
    public static void swap(int[] nums , int a, int b) {
        int t = nums[a];
        nums[a] = nums[b];
        nums[b] = t;
    }
}
